package com.varbal.icegame.algorithms.search;

import java.util.List;

/**
 * 二分法查找
 */
public class BinarySearch {

    /**
     * 出现循环时，
     * 相比于递归，当元素是有限个时，while可能更好一些
     */

    /**
     * 先序遍历、中序遍历、后序遍历，宏观上的区别
     * 先序：输出、左子递归、右子递归
     * 中序：左子递归、输出、右子递归
     * 后序：左子递归、右子递归、输出
     */

    /**
     * 要求：顺序结构、元素可以直接比较，><=
     * @param array
     * @param score
     * @return
     */
    public int binarySearch(int[] array , int score){
        int left , right , mid , NotFind = -1 ;

        if (array[0] >= array[array.length - 1]){
            left = 0;
            right = array.length - 1;
        }else {
            right = 0;
            left = array.length - 1;
        }

        while ( left <= right){
            mid = (left + right) / 2;
            if ( score < array[mid])
                right = mid - 1;
            else if (score > array[mid])
                left = mid + 1;
            else
                return mid;
        }
        return NotFind;
    }
}
